


arr=[1,4,7,1,5,5,3,85,34,75,23,75,2,0]

'''
    这个负责反馈排序分割点在哪里， 同时是排序的具体执行， 此处开始时使用最后一个数做标兵，进行对比，前面的数据， 比标兵的数字小（ arr[i]<arr[last]）， 则将数据交换到前面去，；
    最终找到 这个标兵在这一轮排序后的位置； 交换数据并返回数据；
'''

'''
# 这个也可以，需要注意的是， 交换比标兵数据小的数据到
def mypartition(  arr, firstIndex,  lastIndex):
    i = firstIndex
    for j in range( firstIndex, lastIndex):
        if arr[j]<=arr[lastIndex]:
           temp = arr[i]
           arr[i] = arr[j]
           arr[j] = temp
           i = i + 1
    arr[i],arr[lastIndex]=arr[lastIndex],arr[i]
    return i-1
'''

def mypartition(  arr, firstIndex,  lastIndex):
    i = firstIndex - 1
    for j in range( firstIndex, lastIndex):
        if arr[j]<=arr[lastIndex]:
           i = i + 1
           temp = arr[i]
           arr[i] = arr[j]
           arr[j] = temp
    arr[i+1],arr[lastIndex]=arr[lastIndex],arr[i+1]
    return i

# 此处注意， 左右进行排序时， divIndex， 不要出现重复情况，同时，已确定的divIndex元素，实际上不再进行排序操作
def QuickSortlmx( arr,  firstIndex, lastIndex):
    if( firstIndex<lastIndex):
        divIndex = mypartition( arr, firstIndex, lastIndex)
        QuickSortlmx( arr, firstIndex, divIndex )
        QuickSortlmx( arr, divIndex+1, lastIndex)
    else:
        print('finish once')
        return    

print('before sort arr = ', arr)
QuickSortlmx(arr,0,len(arr)-1)
print('arr = ', arr)

def QuickSort(arr,firstIndex,lastIndex):
    if firstIndex<lastIndex:
        print( 'firstIndex=', firstIndex, ' lastIndex=', lastIndex)
        divIndex=mypartition(arr,firstIndex,lastIndex)
        print( 'divIndex=', divIndex)
        QuickSort(arr,firstIndex,divIndex)
        print("QuickSort left:\n",arr)       
        QuickSort(arr,divIndex+1,lastIndex)
        print("QuickSort right:\n",arr)
    else:
        return

#QuickSort(arr,0,len(arr)-1)
#'''

'''

def QuickSort(arr,firstIndex,lastIndex):
    if firstIndex<lastIndex:
        divIndex=Partition(arr,firstIndex,lastIndex)
        print( 'divIndex=', divIndex)
        QuickSort(arr,firstIndex,divIndex)
        print("QuickSort left:\n",arr)       
        QuickSort(arr,divIndex+1,lastIndex)
        print("QuickSort right:\n",arr)
    else:
        return
 
 
def Partition(arr,firstIndex,lastIndex):
    i=firstIndex-1
    print("Partition firstIndex:",firstIndex, "  lastIndex=",  lastIndex,  "   i=" ,  i)
    for j in range(firstIndex,lastIndex):
        if arr[j]<=arr[lastIndex]:
            i=i+1
            #arr[i],arr[j]=arr[j],arr[i]
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
    arr[i+1],arr[lastIndex]=arr[lastIndex],arr[i+1]
    print("Partition array:\n",arr)
    return i
 
 
arr=[1,4,7,1,5,5,3,85,34,75,23,75,2,0]
 
print("initial array:\n",arr)
QuickSort(arr,0,len(arr)-1)
print("result array:\n",arr)
    
'''

'''
def QuickSort(arr,firstIndex,lastIndex):
    if firstIndex<lastIndex:
        divIndex=Partition(arr,firstIndex,lastIndex)
 
        QuickSort(arr,firstIndex,divIndex)       
        QuickSort(arr,divIndex+1,lastIndex)
    else:
        return
 
 
def Partition(arr,firstIndex,lastIndex):
    i=firstIndex-1
    for j in range(firstIndex,lastIndex):
        if arr[j]<=arr[lastIndex]:
            i=i+1
            arr[i],arr[j]=arr[j],arr[i]
    arr[i+1],arr[lastIndex]=arr[lastIndex],arr[i+1]
    return i
 
 
arr=[1,4,7,1,5,5,3,85,34,75,23,75,2,0]
 
print("initial array:\n",arr)
QuickSort(arr,0,len(arr)-1)
print("result array:\n",arr)

'''